import copy  # 实现深拷贝！！！
import re, random
import sys
from buffer import Buffer
from define_task4 import generate_tasks, nfc_count, task_list, buffer_size

arm_time = 150
sys.setrecursionlimit(1000000)

# stage_list_full = [
#     #[(任务标识)，(操作序号，操作资源，时间，前置任务依赖，(die,page)), (...))
#     ["r1",(1,"nfc1",200,(0,),(1,0)),(2,"arm",1,(1,)),(3,"host",20,(2,))],
#     ["r2",(1,"nfc2",200,(0,),(2,2)),(2,'arm',1,(1,)),(3,'host',20,(2,))],
#     ["w1",(1,"nfc1",200,(0,),(1,1)),(2,"arm",1,(1,)),(3,"host",20,(2,))],
#     ["t",
#         (1,"host",20,(0,)),
#         (2,"nfc1",200,(1,),(1,2)),
#         (3,"arm",1,(2,)),
#         (4,"nfc1",200,(3,),(1,0)),
#         (5,"arm",1,(4,)),
#         (6,"arm",arm_time,(5,)),
#         (7,"nfc2",200,(3,),(2,0)),
#         (8,"arm",1,(7,)),
#         (9,"arm",arm_time,(8,)),
#         (10,"host",20,(6,9,))    
#         ]
# ]

#stage_list_full = 

generate_tasks(10,1,1,1,1,0)
stage_list_full = task_list

file = open('tasks10.txt', 'a')
file.write(str(task_list))
file.write('\n')

random_count = 1000

# 做格式转换
stage_list_lite = []
for task in stage_list_full:
    stages = []
    for stage in task[1:]:  # 遍历处理
        if len(stage) == 5:  # 带了page元组的，末尾加上page
            stage_str = task[0] + "-" + str(stage[0]) + "-" + stage[1] + "-" + str(stage[2]) + "-" + str(stage[3]) + "-" + str(stage[4])
        elif len(stage) == 4:  # 没有带page元组，末尾不加page
            stage_str = task[0] + "-" + str(stage[0]) + "-" + stage[1] + "-" + str(stage[2]) + "-" + str(stage[3]) + "-"
        stages.append(stage_str)
    stage_list_lite.append(stages)


# 下面几个函数专门用于计算执行时间
def init_resourses():  # 用来构造初始状态的可用资源表
    resource = {
        'host': ['0-0<>'],
        'm1': ['0-0<>'],
        'm2': ['0-0<>'],
        'arm': ['0-0<>'],
    }
    for i in range(nfc_count):
        resource['nfc' + str(i)] = ['0-0<>']
    return resource

def init_done_table():  # 用来存储已经完成的stage信息，方便查找所依赖的stage的完成时间
    done_table = {}
    for task in stage_list_full:
        done_table[task[0] + '-0'] = 0
    return done_table

def init_buffer_list():
    buffer_list = []
    for i in range(nfc_count):
        buffer_list.append(Buffer(buffer_size))
    return buffer_list

def compute_order_time(exe_order_str:str):  # 计算每种执行顺序的时间
    resources = init_resourses()  # 算每一种order都要重新构造一个新的
    done_table = init_done_table()  # 初始化一个字典，用来存每个stage的完成时间
    buffer_list = init_buffer_list()  # 分别对应nfc1和nfc2，默认每个buffer深度为1

    stage_list = exe_order_str.split('>>>')
    for stage in stage_list:  # 开始对stage_list中的每一个stage处理，将其放到对应的位置并计算时间
        words = stage.split('-')  # 先做个切割
        unit_name = words[2]  # 此stage所需的器件。之所以要单独存个变量是因为后面如果是matcher的话unit会发生变化
        # 拿前置依赖stage的完成时间和器件的空闲时间，以两者之间较久的那个为准
        # 先查前置依赖的完成时间，便于分配可用器件
        last_depend_done_time = 0
        depend_stages = tuple(eval(words[4]))
        for stage_index in depend_stages:  # 挨个遍历前置依赖
            if done_table[words[0] + '-' + str(stage_index)] > last_depend_done_time:  # 选择完成时间最晚的那一个存下来
                last_depend_done_time = done_table[words[0] + '-' + str(stage_index)]

        # 拿器件空闲时间
        unit_free_time = 0
        if words[2] == 'matcher':  # 需要先分配一个确定的matcher
            matcher1_free_time = int(re.match(r'\d+-(\d+)<\w*', resources['m1'][-1]).group(1))  # 这是m1的
            matcher2_free_time = int(re.match(r'\d+-(\d+)<\w*', resources['m2'][-1]).group(1))  # 这是m2的
            if matcher1_free_time <= matcher2_free_time:  # 如果m1的空闲时间<=m2的，那就分配到m1上
                unit_name = 'm1'
                unit_free_time = matcher1_free_time
            else:  # 分配到m2上
                unit_name = 'm2'
                unit_free_time = matcher2_free_time

        else:  # 不是匹配操作，查resources字典
            last_op = resources[words[2]][-1]  # 拿对应器件的最后执行操作
            unit_free_time = int(re.match(r'\d+-(\d+)<\w*', last_op).group(1))  # 用正则表达式从'0-0<>'中提取出结束时间

        operation_time = int(words[3])
        # 检查buffer命中情况
        if words[5]:  # 如果是需要buffer的
            buffer_info = tuple(eval(words[5]))  # (dieNo, page)
            buffer_instance = buffer_list[buffer_info[0] - 1]  # 先拿到对应channel的buffer instance
            if buffer_instance.is_hit(buffer_info[1]):  # 如果buffer命中了
                operation_time = 0
            else:  # 未命中，则先分配一个
                if not buffer_instance.allocate(buffer_info[1]):  # allocate返回了False，说明需要先进行写回
                    operation_time += 600  # 增加一段写回的时间
            if words[0].startswith('w') or words[0].startswith('写'):  # 如果是一个host写操作，则需要将buffer置脏
                buffer_instance.mark_dirty(buffer_info[1])
        
        # 接下来就需要计算stage的起始-终止时间了，并保存结果
        start_time = last_depend_done_time if last_depend_done_time > unit_free_time else unit_free_time  # 确定起始时间
        end_time = start_time + operation_time  # 确定结束的时间
        # 记录结果
        resources[unit_name].append(str(start_time) + '-' + str(end_time) + '<' + words[0] + '-' + words[1] + '>')  # 添加到器件时间表中
        done_table[words[0] + '-' + words[1]] = end_time  # 标记此stage的完成时间，便于下次拿前置stage的完成时间

    # 统计此order的最终执行时间
    total_time = sorted(done_table.items(), key = lambda kv:(kv[1], kv[0]))[-1][1]  # 直接对done_table按值排序即可拿到完成时间最晚的那个stage
    return total_time


def generate_order(order_str:str, remanent_tasks:list):  # 递归函数
    # 判断remanent_tasks是否为空，空的话就结束递归
    remanent_tasks_is_empty = True  # 先假设是空的
    for task in remanent_tasks:
        if len(task) > 0:
            remanent_tasks_is_empty = False
            break
    if remanent_tasks_is_empty:
        time = compute_order_time(order_str[:-3])  # 先计算下序列所需要的执行时间
        return (time, order_str[:-3])  # 结束递归，向上返回

    remanent_tasks_copy = copy.deepcopy(remanent_tasks)  # 在下面的候选池提取环节中会破坏列表，所有先深拷贝一份，然后在副本上操作
    usable_stages = []  # 先初始化一个空池子
    # 从remanent_tasks_copy中找出所有可用的stage放到候选池中去
    for remanent_task_index in range(len(remanent_tasks_copy)):  # 遍历每一个剩余的task
        # 只管task不为空的情况，空着就空着吧，不要删，否则接下来检查前置的时候没法从任务表中定位任务
        while remanent_tasks_copy[remanent_task_index]:  # 在不为空的task中一直找下去，把能拿的都拿到候选池中
            stage_words = remanent_tasks_copy[remanent_task_index][0].split('-')  # 取第一个stage做个切割，拿其前置依赖
            depend_table = tuple(eval(stage_words[4]))  # 转换得到依赖表
            this_stage_can_be_issue = True  # 先假设此stage的前置依赖都做完了，可以放到候选池中发射
            for depend_stage_num in depend_table:  # 检查依赖
                # 实际上，如果是任务的第一个stage，那么depend_stage_num - 1后会得到-1，从而指向最后一个stage，但不影响功能
                if stage_list_lite[remanent_task_index][depend_stage_num - 1] in usable_stages:  # 如果所依赖的stage在候选池里，那么说明其前置未完成，此stage不能发射
                    this_stage_can_be_issue = False
                    break  # 不用再看后面的依赖了
            if this_stage_can_be_issue:  # 如果此stage可以放到候选池里等待发射
                usable_stages.append(remanent_tasks_copy[remanent_task_index][0])  # 把这个stage放到候选池里
                remanent_tasks_copy[remanent_task_index] = remanent_tasks_copy[remanent_task_index][1:]  # 利用切片的方法将stage从剩余stages中剔除
            else:  # 此stage不能放到候选池中
                break  # 那就离开这个task

    stage = random.choice(usable_stages)  # 从候选池中拿一个stage
    new_order_str = order_str + stage + '>>>'  # 此处不能在原order_str上进行操作，否则下次循环还会保留上次的结果
    for task in remanent_tasks:
        if stage in task:
            task.remove(stage)
            break
    return generate_order(new_order_str, remanent_tasks)  # 进入下一层的递归

best_time = 9999999
best_order = ''
for i in range(random_count):
    time, order_str = generate_order('', copy.deepcopy(stage_list_lite))  # 先算所有的合法排列
    if time < best_time:
        best_time = time
        best_order = order_str
print(best_time)
compute_order_time(best_order)
file.write(str(best_time))
file.close()
